/*
 * @lc app=leetcode.cn id=475 lang=cpp
 *
 * [475] 供暖器
 */

// @lc code=start
class Solution
{
public:
    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        //一条线 多个圈覆盖所有范围
        //找到所有东西距离最近的圆心的最短距离
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int res = 0;
        //寻找
        for (int i = 0; i < houses.size(); i++)
        {
            int right = heaters[heaters.size() - 1];
            int left = 0;
            for (int j = 0; j < heaters.size(); j++)
            {
                //找到第一个右边的
                if (heaters[j] >= houses[i])
                {
                    right = heaters[j]; //第一个右边的
                }
            }
            left = right - 1;
            //如果没有找到更大的 right为最右边的供暖
            //如果只有一个供暖器那么left = -1 right =0
            if (left = -1)
            {
                //只有一个供暖
                res = max(res, abs(houses[i] - heaters[0]));
            }
            else
            {
                //能找到两个供暖
                res = max(res, min(abs(houses[i] - heaters[left]),
                                   abs(houses[i] - heaters[right])));
            }
        }
        return res;
    }
};
// @lc code=end
